package pri.zjy.tree;

import pri.zjy.tree.model.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author zhangjy
 * @description 二叉树的层序遍历 II
 * <p>
 * 给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历
 * @date 2025/3/28 10:34
 */
public class LevelOrderBottom_107 {

    public static void main(String[] args) {

    }

    /**
     * 个解：先正常层序遍历，再反转
     * <p>
     * T(n) = O(n)；其中 n 是二叉树中的节点个数。每个节点访问一次，因此访问节点时间复杂度是 O(n)，另外，翻转ans时间复杂度也是O(n)，因此时间总复杂度为O(n)。
     * S(n) = O(n)；其中 n 是二叉树中的节点个数。空间复杂度取决于队列开销，队列中的节点个数不会超过 n。
     */
    public List<List<Integer>> levelOrderBottom2(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) return ans;

        List<Integer> levelVals;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        // 先记录自上而下层序遍历
        while (!queue.isEmpty()) {
            levelVals = new ArrayList<>();
            int currentLevelSize = queue.size();
            for (int i = 0; i < currentLevelSize; i++) {
                TreeNode poll = queue.poll();
                // 记录本层节点值
                levelVals.add(poll.val);
                // 下层节点入队
                if (poll.left != null) queue.offer(poll.left);
                if (poll.right != null) queue.offer(poll.right);
            }
            ans.add(levelVals);
        }

        // 再反转ans
        int i = 0, j = ans.size() - 1;
        while (i < j) {
            levelVals = ans.get(j);
            ans.set(j, ans.get(i));
            ans.set(i, levelVals);
            i++;
            j--;
        }
        return ans;
    }

    /**
     * 同官解；
     * <p>
     * 分析：
     * <p>
     * 题目要求返回的节点值是 自下而上、从左向右 顺序，这并不意味着解题时要从叶子节点这一层这个顺序去遍历。
     * <p>
     * 简单思考下，如果要从叶子节点层遍历，首先要找到最下层，就要遍历完整棵树；
     * <p>
     * 找到后要从下往上遍历，就需要记录当前层的根节点，这不现实；
     * <p>
     * 所以，我们仍然可以自上而下、从左到右遍历，只不过记录元素值时，把本层所有元素都放到结果集res的第一位即可，这样就能保证res的顺序是自下而上顺序存放。
     *
     * <p>
     * 为什么用LinkedList，而不是和层序遍历一样使用ArrayList？
     * <p>
     * 因为，若底层是数组，结果集res每次记录到数组首位时，会涉及大量移动操作，时间复杂度高；而是链表，插入、删除的时间复杂度都是O(1)。
     *
     * <p>
     * 注意
     * <p>
     * 对于，List<String> list1 = new LinkedList<>(); 由源码可知：
     * 头插法：list1.add(0, "sss");
     * 尾插法：list1.add(list.size(), "sss");
     * <p>
     * 而对于，LinkedList<String> list2 = new LinkedList<>();
     * 头插法：list2.addFirst()；
     * 尾插法：list2.addLast()；
     * <p>
     * T(n) = O(n)；其中 n 是二叉树中的节点个数。每个节点访问一次，结果列表使用链表的结构时，在结果列表头部添加一层节点值的列表的时间复杂度是 O(1)，因此总时间复杂度是 O(n)。
     * S(n) = O(n)；其中 n 是二叉树中的节点个数。空间复杂度取决于队列开销，队列中的节点个数不会超过 n。
     */
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new LinkedList<>();
        if (root == null) return res;

        // 已记录元素的节点
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> vals = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                vals.add(node.val);

                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            // 头插法
            res.add(0, vals);
        }

        return res;
    }

}
